#ifndef _geo_segment_h_
#define _geo_segment_h_

#include <iostream>
#include <geo/point.h>
#include <math/fraction.h>

namespace contest
{

/**
 * 2D segment is a collection of two points.
 * @template T: Type of coordinates (i.e. int, int64_t, float, double, fraction)
 **/
template <class T> class segment
{
public:
    point<T> p;
    point<T> q;
    segment(): p(), q()
    {
    }
    segment(const point<T>& a, const point<T>& b): p(a), q(b)
    {
    }
    segment(const segment<T>& rhs): p(rhs.p), q(rhs.q)
    {
    }
    /**
     * Segment to segment intersection.
     * @param rhs: Another segment.
     * @param intersection: If intersection, the point of intersection.
     * @return: True if segments intersect in a single point.
     * @see: http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
     **/
    template <class D> bool intersection(const segment<T>& rhs, point<D>& intersection) const
    {
        const segment<T>& p = *this;
        const segment<T>& q = rhs;
        const vector<T> r = p.q - p.p;
        const vector<T> s = q.q - q.p;
        const vector<T> qp= q.p - p.p;
        T rxs = r.cross(s);
        if (rxs==0)
            return false;
        T t = qp.cross(s);
        T u = qp.cross(r);
        // 0 <= t/rxs <= 1 && 0 <= u/rxs <= 1
        if (rxs > 0)
        {
            if (t < 0 || t > rxs || u < 0 || u > rxs)
                return false;
        }
        else
        {
            if (t > 0 || t < rxs || u > 0 || u < rxs)
                return false;
        }
        //Done in this way to use the overloaded class D
        intersection.x = r.x*t;
        intersection.x/= rxs;
        intersection.x+= p.p.x;
        intersection.y = r.y*t;
        intersection.y/= rxs;
        intersection.y+= p.p.y;
        return true;
    } 
    friend std::ostream& operator<<(std::ostream& out, const segment<T>& s)
    {
        std::cout<<"("<<s.p.x<<","<<s.p.y<<")"<<"("<<s.q.x<<","<<s.q.y<<")";
    }
};

void testSegment()
{
    typedef point<int> point_t;
    typedef segment<int> segment_t;
    typedef point<fraction> intersection_t;

    segment_t l1(point_t(27, 44), point_t(12, 32));
    segment_t l2(point_t(46, 53), point_t(17, 62));
    segment_t l3(point_t(46, 70), point_t(22, 40));

    intersection_t it;
    bool flag;
    flag = l1.intersection(l2, it);
    assert(flag == false);
    flag = l2.intersection(l1, it);
    assert(flag == false);
    flag = l2.intersection(l3, it);
    assert(flag == true);
    std::cout<<it<<std::endl;
    flag = l1.intersection(l3, it);
    assert(flag == true);
    std::cout<<it<<std::endl;
}

}

#endif
